package com.fyl.basic_algorithm.tree;

/**
 * @author 冯永龙
 * @date 2021/3/31 14:33
 */
public class BinarySearchTree {
    private Node tree;

    //查找
    public Node find(int data) {
        Node p = tree;
        while (p != null) {
            if (data < p.data) {
                p = p.left;
            } else if (data > p.data) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }

    //插入
    public void insert(int data) {
        if (tree == null) {
            tree = new Node(data);
            return;
        }

        Node p = tree;
        while (p != null) {
            if (data > p.data) {
                if (p.right == null) {
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            } else {
                if (p.left == null) {
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            }
        }
    }

    public void delete(int data) {
        Node p = this.tree; //p指向要删除的节点，初始化指向根节点
        Node parent = null; //p的父亲节点

        //寻找删除的节点
        while (p != null && p.data != data) {
            parent = p;
            if (data > p.data) {
                p = p.right;
            } else {
                p = p.left;
            }
        }

        if (p == null) return;

        //要删除的节点有两个子节点
        if (p.left != null && p.right != null) { //查找右子树的最小节点
            Node min = p.right;
            Node parentMin = p; //min的父节点

            while (min.left != null) {
                parentMin = min;
                min = min.left;
            }

            p.data = min.data; //将min的数据替换到p
            p = min;   //数据交换后就转换为删除min节点
            parent = parentMin;
        }

        //删除节点是叶子节点或者仅有一个子节点
        Node child;  //p的子节点
        if (p.left != null) {
            child = p.left;
        } else if (p.right != null) {
            child = p.right;
        }else {
            child =null;
        }

        if (parent==null) {
            tree = child; //删除的是根节点
        }else if (parent.left==p){
            parent.left = child;
        }else {
            parent.right = child;
        }
    }

    //找到最大值
    public Node findMax() {
        if (tree == null) return null;
        Node p = tree;

        while (p.right != null) {
            p = p.right;
        }

        return p;
    }

    //找到最小值
    public Node findMin() {
        if (tree == null) return null;
        Node p = tree;

        while (p.left != null) {
            p = p.left;
        }

        return p;
    }

    public static class Node {
        private int data;
        private Node left;
        private Node right;

        public Node(int data) {
            this.data = data;
        }
    }
}
